package 代码随想录_贪心算法;

/**
 * @author zx
 * @create 2022-07-12 23:54
 *
 * 这道题目一定是要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼
 * 此时局部最优：只要右边评分比左边大,右边的孩子就多一个糖果,全局最优：相邻的孩子中,评分高的右孩子获得比左边孩子更多的糖果
 * 局部最优可以推出全局最优
 * 先确定右边评分大于左边的情况(也就是从前向后遍历)
 * 确定左孩子大于右孩子的情况一定要从后向前遍历！
 * 如果从前向后遍历,根据ratings[i + 1]来确定ratings[i]对应的糖果,那么每次都不能利用上前一次的比较结果
 */
public class 分发糖果_135 {
    /**
     分两个阶段
     1.起点下标 1 从左往右,只要右边比左边大,右边的糖果 = 左边 + 1
     2.起点下标ratings.length - 2从右往左,只要左边比右边大,此时左边的糖果应该取本身的糖果数(符合比它左边大)和
       右边糖果数 + 1二者的最大值,这样才符合它比它左边的大,也比它右边大
     */
    public int candy(int[] ratings) {
        int[] arr    = new int[ratings.length];
        for(int i = 0;i < arr.length;i++){
            arr[i] = 1;//初始化,每个人至少一个糖果
        }
        for(int i = 1;i < ratings.length;i++){
            if(ratings[i] > ratings[i - 1]){
                arr[i] = arr[i - 1] + 1;
            }
        }
        for(int i = ratings.length - 2;i >= 0;i--){
            if(ratings[i] > ratings[i + 1]){
                arr[i] = Math.max(arr[i],arr[i + 1] + 1);
            }
        }
        int res = 0;
        for(int i = 0;i < arr.length;i++){
            res += arr[i];
        }
        return res;
    }
}
